/* eslint-disable unicorn/prefer-ternary */
/* eslint-disable jsdoc/no-restricted-syntax */
"use strict";

// / function LCSLength(X[1..m], Y[1..n])
//    C = array(0..m, 0..n)
//    for i := 0..m
//        C[i,0] = 0
//    for j := 0..n
//        C[0,j] = 0
//    for i := 1..m
//        for j := 1..n
//            if X[i] = Y[j]
//                C[i,j] := C[i-1,j-1] + 1
//            else
//                C[i,j] := max(C[i,j-1], C[i-1,j])
//    return C[m,n]
// /
/* cSpell:ignoreRegExp "\w+" */
const X = [..."XMJYAUZ"];
const Y = [..."MZJAWXU"];
// -> "MJAU"
const C = Array.from({ length: X.length + 1 }, () =>
  Array.from({ length: Y.length + 1 }).fill(0),
);

// console.log(C);

/**
 * @param {any[]} X
 * @param {any[]} Y
 * @param {number} m
 * @param {number} n
 * @returns {number}
 */
function patchTableLCSLength(X, Y, m = X.length, n = Y.length) {
  // 动态规划填充表格
  for (let i = 1; i <= m; i += 1) {
    for (let j = 1; j <= n; j += 1) {
      if (X[i - 1] === Y[j - 1]) {
        // 注意索引转换：伪代码的 X[1..m] 对应 JS 的 X[0..m-1]
        C[i][j] = C[i - 1][j - 1] + 1;
      } else {
        C[i][j] = Math.max(C[i][j - 1], C[i - 1][j]);
      }
    }
  }

  return C[m][n]; // 返回最长公共子序列的长度
}
console.log(patchTableLCSLength(X, Y)); // 输出: 4 (对应子序列 "BCAB" 或 "BDAB")

/** ----------------------------------------------------------*/
/**
 * @param {any[][]} C
 * @param {any[]} X
 * @param {any[]} Y
 * @param {number} i
 * @param {number} j
 * @returns {string}
 */
function backtrack(C, X, Y, i = X.length, j = Y.length) {
  if (i === 0 || j === 0) {
    return "";
  } else if (X[i] && Y[i] && X[i] === Y[j]) {
    return backtrack(C, X, Y, i - 1, j - 1) + X[i];
  } else if (C[i][j - 1] > C[i - 1][j]) {
    return backtrack(C, X, Y, i, j - 1);
  }
  return backtrack(C, X, Y, i - 1, j);
}
console.log(backtrack(C, X, Y));
/** ----------------------------------------------------------*/
// /**
//  * @param C {any[][]}
//  * @param X {any[]}
//  * @param Y {any[]}
//  * @param {number} i
//  * @param {number} j
//  *
//  */
// function backtrackAll(C, X, Y, i, j){
// if (i = 0 || j = 0)
// return ""
// if X[i] = Y[j]
//     return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
// R := {}
// if C[i,j-1] ≥ C[i-1,j]
//     R := backtrackAll(C, X, Y, i, j-1)
// if C[i-1,j] ≥ C[i,j-1]
//     R := R ∪ backtrackAll(C, X, Y, i-1, j)
// return R
// }
/** ----------------------------------------------------------*/
/**
 * @param {any[][]} C
 * @param {any[]} X
 * @param {any[]} Y
 * @param {number} i
 * @param {number} j
 */
function printDiff(C, X, Y, i = X.length + 1, j = Y.length + 1) {
  if (i >= 0 && j >= 0 && X[i] === Y[j]) {
    printDiff(C, X, Y, i - 1, j - 1);
    console.log(`  ${X[i]}`);
  } else if (j > 0 && (i === 0 || C[i][j - 1] >= C[i - 1][j])) {
    printDiff(C, X, Y, i, j - 1);
    console.log(`+ ${Y[j]}`);
  } else if (i > 0 && (j === 0 || C[i][j - 1] < C[i - 1][j])) {
    printDiff(C, X, Y, i - 1, j);
    console.log(`- ${X[i]}`);
  } else {
    console.log("");
  }
}

if (module === require.main) {
  printDiff(C, X, Y, X.length - 1, Y.length - 1);
}
/** ----------------------------------------------------------*/

module.exports = { LCSLength: patchTableLCSLength, backtrack };
